package pers.qianyu.month_202012.date_20201222;

import org.junit.*;

import java.util.*;

/**
 * 堆排序练习
 *
 * @author mizzle rain
 * @date 2020-12-22 15:26
 */
public class HeapSortTest {
    public void heapSort(int[] arr) {
        int len = arr.length;
        for (int i = (len >> 1) - 1; i >= 0; i--) {
            adjustHeap(arr, i, len);
        }
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 从小到大排序的话，需要构造大顶堆
     * 性质：
     * - 二叉堆使用数组来表示的话，一个节点的左右孩子的索引为 2 * i + 1 和 2 * i + 2
     * - 第一个非叶子节点的索引为 len / 2 - 1
     *
     * @param len 需要调节的堆为数组 [start ... len）
     */
    private void adjustHeap(int[] arr, int start, int len) {
        // 直到最后一个叶子节点即可
        for (int cur = start; cur <= (len >> 1) - 1; cur++) {
            int index = 2 * cur + 1;
            if (index + 1 < len && arr[index + 1] > arr[index]) {
                index++;
            }
            if (arr[index] > arr[cur]) {
                // 子节点大于当前节点就交换
                swap(arr, cur, index);
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test1() {
        int[] arr = {26, 58, 70, 45, 98, 31, 66, 72, 15, 33};
        new HeapSortTest().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void testHeapSort() {
        for (int item = 0; item < 20; item++) {
            int[] arr = new int[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * 100);
            }
            System.out.println(Arrays.toString(arr));
            int[] newArr = Arrays.copyOf(arr, arr.length);
            new HeapSortTest().heapSort(arr);
            Arrays.sort(newArr);
            System.out.println(Arrays.toString(arr) + "\n");
            Assert.assertArrayEquals(arr, newArr);
        }
    }
}
